package org.example.myleet.p508;

import org.example.myleet.Utils.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {

    private int maxCount;
    private HashMap<Integer, Integer> sumCountMap;

    public int[] findFrequentTreeSum(TreeNode root) {
        maxCount = 0;
        sumCountMap = new HashMap<>();
        walkTree(root);
        List<Integer> answer = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : sumCountMap.entrySet()) {
            if (maxCount == entry.getValue()) {
                answer.add(entry.getKey());
            }
        }
        int[] ans = new int[answer.size()];
        for (int i = 0; i < answer.size(); ++i) {
            ans[i] = answer.get(i);
        }
        return ans;
    }

    private int walkTree(TreeNode node) {
        if (null == node.left && null == node.right) {
            int sumCount = sumCountMap.getOrDefault(node.val, 0) + 1;
            maxCount = Math.max(maxCount, sumCount);
            sumCountMap.put(node.val, sumCountMap.getOrDefault(node.val, 0) + 1);
            return node.val;
        }
        int sum = node.val;
        if (null != node.left) {
            sum += walkTree(node.left);
        }
        if (null != node.right) {
            sum += walkTree(node.right);
        }
        int sumCount = sumCountMap.getOrDefault(sum, 0) + 1;
        maxCount = Math.max(maxCount, sumCount);
        sumCountMap.put(sum, sumCount);
        return sum;
    }
}
